package search;

/**
 * 插值查找
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
        int index =Search(arr,0,arr.length-1,9);
        if(index!=-1)
        System.out.println("value="+arr[index]);
        else
            throw new RuntimeException("未找到");
    }
    private static int Search(int[] arr, int lift, int right, int value){
        if(lift>right||value>arr[arr.length-1]||value<arr[0]){
            return -1;
        }
        int mid=lift+(right-lift)*(value-arr[lift])/(arr[right]-arr[lift]);
        int midVal = arr[mid];
        if(value<midVal){
            return Search(arr,lift,mid-1,value);
        }else if(value>midVal){
            return Search(arr,mid+1,right,value);
        }else{
            return mid;
        }
    }
}
